package arithmetic2;

/**
 * @author Ajie
 * @date 5/5/21
 * @function
 * 543. 二叉树的直径
 * 难度
 * 简单
 *
 * 693
 *
 * 收藏
 *
 * 分享
 * 切换为英文
 * 接收动态
 * 反馈
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 */
public class T_543_DiameterOfBinaryTree {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        System.out.println(diameterOfBinaryTree(treeNode));
    }

    public static int res=0;
    public static int diameterOfBinaryTree(TreeNode root) {
        //dp r = max(dp.left , dp.right)+1;
        //res = max(res,left+right)
        if(root == null ){
            return 0;
        }
        res = 0;
        dfs(root);
        return res;
    }

    public static int dfs(TreeNode root){
        if(root == null ){
            return 0;
        }
        int resLeft =  dfs(root.left);

        int resRight = dfs(root.right);

        // if(resLeft!=0 && resRight!=0){//输入：[1],输出：1, 预期结果：0
        //  res = Math.max(res,resLeft+resRight);
        // }
        res = Math.max(res,resLeft+resRight);

        return Math.max(resLeft,resRight)+1;
    }
}
